#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 2005;
long long c[maxn][maxn];
long long s[maxn][maxn];
int t,k;

inline void read(int &x){
    char c;int flag=0;
    while(!isdigit(c=getchar()))
      if(c=='-') flag=1;
    x=c-'0';
    while(isdigit(c=getchar()))
      x=x*10+c-'0';
    if(flag) x=-x;
}

inline void js(int a){
	for(register int i = 0; i <= a; i++) {
  		c[i][0] = 1;
  		for(int j = 1; j <= i; j++) c[i][j] = (c[i-1][j-1] + c[i-1][j])%k;
	}
	
	for(register int i=0;i<=a;i++){
		for(register int j=0;j<=a;j++){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			if(c[i][j]==0 && j<=i)s[i][j]++;
		}  
	}
}

int main(){
	int n,m;
	read(t);
	read(k);
	js(2000); 
	while(t--){
		read(n);
		read(m);
		cout<<s[n][m]<<endl;
	}
	return 0;
} 
